package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC677 {
    public long startExecuteTime = System.currentTimeMillis();


    class MapSum {
        private class TrieNode {
            private int val;
            private TrieNode[] next;

            public TrieNode(int val) {
                this.val = val;
                next = new TrieNode[26];
            }
        }

        private TrieNode root;
        private int ch;
        private int res;

        /**
         * Initialize your data structure here.
         */
        public MapSum() {
            root = new TrieNode(0);
        }

        public void insert(String key, int val) {
            TrieNode nNode = root;
            for (int i = 0; i < key.length(); i++) {
                ch = key.charAt(i) - 'a';
                if (nNode.next[ch] == null) {
                    nNode.next[ch] = new TrieNode(0);
                }
                nNode = nNode.next[ch];
            }
            nNode.val = val;
        }

        public int sum(String prefix) {
            TrieNode nNode = root;
            for (int i = 0; i < prefix.length(); i++) {
                ch = prefix.charAt(i) - 'a';
                if (nNode.next[ch] == null) {
                    return 0;
                }
                nNode = nNode.next[ch];
            }
            res = 0;
            dfs(nNode);
            return res;
        }

        private void dfs(TrieNode nNode) {
            if (nNode == null) {
                return;
            }
            res += nNode.val;
            for (TrieNode tNode : nNode.next) {
                dfs(tNode);
            }
        }
    }

    public void run() {
        MapSum solution = new MapSum();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC677 an = new LC677();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
